package algorithm.shortestpath;

import java.util.Stack;
import java.util.Vector;

/**
 * @author bingo
 * @Description     迪杰斯特拉算法
 * @Date 2018/4/30
 */
public class Dijkstra <Weight extends Number & Comparable> {

    /**图的引用*/
    private WeightedGraph G;
    /**起始点*/
    private int s;
   /**起始点到i的最小路径*/
    private Number[] distTo;
    /**访问标记，表示为i位置的节点是否被访问过*/
    private boolean[] marked;
    /**from[i]记录最短路径中，到达i点的路径*/
    private Edge<Weight>[] from;

    public Edge<Weight>[] getFrom() {
        return from;
    }

    public Dijkstra(WeightedGraph g, int s) {
        this.G = g;
        this.s = s;
        distTo = new Number[G.V()];
        marked = new boolean[G.V()];
        from = new Edge[G.V()];
        for(int i=0;i<G.V();i++){
           distTo[i] =0.0;
           marked[i] = false;
           from[i] = null;
        }

        IndexMinHeap  mih = new IndexMinHeap(G.V());
        distTo[s] = 0.0;
        marked[s] = true;
        from[s] = new Edge<Weight>(s,s, (Weight)(Number) 0.0);
        mih.insert(s,(Weight)distTo[s]);
        while (!mih.isEmpty()){
            int v= mih.extractMinIndex();
            marked[v] = true;
            for(Object e :G.adj(v)){
                Edge<Weight> edge = (Edge<Weight>) e;
                int w = edge.getOther(v);
                boolean flag = marked[w];
                if(!flag){
                    if(from[w] == null ||distTo[v].doubleValue()+edge.wt().doubleValue()<distTo[w].doubleValue()){
                     distTo[w] = distTo[v].doubleValue()+edge.wt().doubleValue();
                     from[w] = edge;
                     if(mih.contain(w)){
                         mih.change(w,(Weight)distTo[w] );
                     }
                     else{
                          mih.insert(w,(Weight)distTo[w] );
                      }
                    }
                }
            }

        }

    }
 /**返回s-w的最短路径*/
    public Number shortPath(int w){
        return  distTo[w];
    }

    /**起点s--w是否是联通的*/
    public boolean hasPathTo(int w){

        return marked[w];
    }

    public Vector shortestPath(int w){
        Stack<Edge<Weight>> s = new Stack<>() ;
        Edge edge= from[w];
        System.out.println("edge.a()--"+edge.a());
         while (edge.a()!=this.s){
          s.push(edge);
          edge = from[edge.a()];
          }
          s.push(edge);
        Vector<Edge<Weight>> vector = new Vector();
        while(!s.isEmpty()){
            vector.add(s.pop());
        }

        return vector;

    }
    void showPath(int w){
        assert w >= 0 && w < G.V();
        assert hasPathTo(w);
        Vector<Edge<Weight>> path =  shortestPath(w);
        for( int i = 0 ; i < path.size() ; i ++ ){
            System.out.print( path.elementAt(i).a() + " -> ");
            if( i == path.size()-1 )
                System.out.println(path.elementAt(i).b());
        }
    }

}
